<html>
<head>
<link rel="shortcut icon" href="./favicon.ico">
<link rel="stylesheet" type="text/css" href="./style.css">
<link rel="canonical" href="./Bit_Shifter_Pipelined.html">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="This module is a building block for application-specific shifts and rotates. It synthesizes to LUT logic and Skid Buffers and can be quite large if not specialized to a particular situation.">
<title>Bit Shifter Pipelined</title>
</head>
<body>

<p class="inline bordered"><b><a href="./Bit_Shifter_Pipelined.v">Source</a></b></p>
<p class="inline bordered"><b><a href="./legal.html">License</a></b></p>
<p class="inline bordered"><b><a href="./index.html">Index</a></b></p>

<h1>Bit Shifter (Pipelined)</h1>
<p>This module is a building block for application-specific shifts and
 rotates. It synthesizes to LUT logic and Skid Buffers and can be quite
 large if not specialized to a particular situation.</p>
<p>We can treat the <code>shift_amount</code> and the <code>shift_direction</code> together as
 a signed magnitude number: the amount is an absolute value, and the
 direction is the sign of the value. Here, a <code>shift_direction</code> of <code>1</code>,
 meaning a negative number, shifts to the right. Choosing this convention
 for the sign matches the behaviour of a shift when we think about it as
 a multiplication or division by a power of 2:</p>
<ul>
<li>Multipliying by 8 is equivalent to 2<sup>3</sup>N, which is
 a shift-left by 3 steps.</li>
<li>Dividing N by 4 is equivalent to 2<sup>-2</sup>N, which is
 a shift-right by 2 steps.</li>
</ul>
<p>Adding together these multiples and fractions generated by the shifts
 enables the creation of small, cheap scaling by constant ratios:</p>
<ul>
<li>3N = N + 2<sup>1</sup>N</li>
<li>10N = 8N + 2N = 2<sup>3</sup>N + 2<sup>1</sup>N</li>
<li>5N/4 = N + N/4 = N + 2<sup>-2</sup>N</li>
<li>etc...</li>
</ul>
<p>When the shift values are constant, the shifter reduces to simple rewiring,
 which in turn reduces the above examples to an adder or two each.</p>
<p>The shifts are internally unsigned and <code>word_in</code> and <code>word_out</code> are
 extended to the left and right so new bits can be shifted in and current
 bits shifted out without loss, regardless of shift amount or direction,
 which enables the creation of more complex shifts or rotates:</p>
<ul>
<li>Wire the most-significant bit (MSB) of <code>word_in</code> to all <code>word_in_left</code> inputs and zero to all <code>word_in_right</code> inputs to create a signed arithmetic shift.</li>
<li>Wire the <code>word_in</code> MSB to <code>word_in_right</code> MSB (or vice-versa) to create a rotate function.</li>
<li>Feed <code>word_out_left</code> and <code>word_out</code> to a double-word adder and set the
 shift to +1 (left by 1) as part of the construction of a conditional-add
 multiplier, which multiplies two N-bit words in N cycles, giving a 2N-bit
 result.</li>
</ul>

<pre>
`default_nettype none

module <a href="./Bit_Shifter_Pipelined.html">Bit_Shifter_Pipelined</a>
#(
    parameter   WORD_WIDTH  = 0,
    parameter   PIPE_DEPTH  = 0
)
(
    input   wire                        clock,
    input   wire                        clear,

    input   wire                        input_valid,
    output  wire                        input_ready,

    input   wire    [WORD_WIDTH-1:0]    word_in_left,
    input   wire    [WORD_WIDTH-1:0]    word_in,
    input   wire    [WORD_WIDTH-1:0]    word_in_right,

    input   wire    [WORD_WIDTH-1:0]    shift_amount,
    input   wire                        shift_direction, // 0/1 -> left/right

    output  wire                        output_valid,
    input   wire                        output_ready,

    output  reg     [WORD_WIDTH-1:0]    word_out_left,
    output  reg     [WORD_WIDTH-1:0]    word_out,
    output  reg     [WORD_WIDTH-1:0]    word_out_right
);
</pre>

<p>Let's document the shift direction convention again here, and define our
 initial values for the outputs and the intermediate result.</p>

<pre>
    localparam  LEFT_SHIFT  = 1'b0;

    localparam  TOTAL_WIDTH = WORD_WIDTH * 3;
    localparam  TOTAL_ZERO  = {TOTAL_WIDTH{1'b0}};
    localparam  WORD_ZERO   = {WORD_WIDTH{1'b0}};

    localparam PIPE_WIDTH   = TOTAL_WIDTH + WORD_WIDTH + 1;

    initial begin
        word_out_left    = WORD_ZERO;
        word_out         = WORD_ZERO;
        word_out_right   = WORD_ZERO;
    end 
</pre>

<p>Pipeline the inputs, which should then retime into the shift logic.</p>

<pre>
    wire [WORD_WIDTH-1:0] word_in_left_pipelined;
    wire [WORD_WIDTH-1:0] word_in_pipelined;
    wire [WORD_WIDTH-1:0] word_in_right_pipelined;
    wire [WORD_WIDTH-1:0] shift_amount_pipelined;
    wire                  shift_direction_pipelined;

    <a href="./Skid_Buffer_Pipeline.html">Skid_Buffer_Pipeline</a>
    #(
        .WORD_WIDTH (PIPE_WIDTH),
        .PIPE_DEPTH (PIPE_DEPTH)
    )
    bit_shift_pipeline
    (
        // If PIPE_DEPTH is zero, these are unused
        // verilator lint_off UNUSED
        .clock          (clock),
        .clear          (clear),
        // verilator lint_on  UNUSED
        .input_valid    (input_valid),
        .input_ready    (input_ready),
        .input_data     ({word_in_left, word_in, word_in_right, shift_amount, shift_direction}),

        .output_valid   (output_valid),
        .output_ready   (output_ready),
        .output_data    ({word_in_left_pipelined, word_in_pipelined, word_in_right_pipelined, shift_amount_pipelined, shift_direction_pipelined})
    );
</pre>

<p>Rather than do arithmetic and calculate slices of vectors to figure out
 where the shifted bits end up, let's concatenate the input words into one
 triple-wide word, shift it as an unsigned number, then deconcatenate the
 result into each output word. All we have to do is keep the same convention
 on bit significance: here LSB is on the right.</p>

<pre>
    reg [TOTAL_WIDTH-1:0] word_in_total = TOTAL_ZERO;

    always @(*) begin
        word_in_total = {word_in_left_pipelined, word_in_pipelined, word_in_right_pipelined};
        {word_out_left, word_out, word_out_right} = (shift_direction_pipelined == LEFT_SHIFT) ? word_in_total << shift_amount_pipelined : word_in_total >> shift_amount_pipelined; 
    end

endmodule
</pre>

<hr>
<p><a href="./index.html">Back to FPGA Design Elements</a>
<center><a href="https://fpgacpu.ca/">fpgacpu.ca</a></center>
</body>
</html>

